package interviewpreparationkit.array

/**
 * [Minimum Swaps 2](https://www.hackerrank.com/challenges/minimum-swaps-2)
 */
// Complete the minimumSwaps function below.
fun minimumSwaps(arr: Array<Int>): Int {
    var swapCount = 0

    fun swap(arr: Array<Int>, m: Int, n: Int) {
        swapCount++
        val temp: Int = arr[m]
        arr[m] = arr[n]
        arr[n] = temp
    }

    fun indexOf(arr: Array<Int>, element: Int, start: Int): Int {
        for (i in start until arr.size) {
            if (element == arr[i]) {
                return i
            }
        }
        return -1
    }

    var expected: Int
    var expectedOffset = 1
    for (i in 0 until arr.size) {
        var j = -1
        while (j < 0) {
            expected = i + expectedOffset
            if (arr[i] != expected) {
                j = indexOf(arr, expected, i + 1)
                if (j < 0) {
                    expectedOffset++
                } else {
                    swap(arr, i, j)
                }
            } else {
                j = i
            }
        }

    }
    return swapCount
}